#ifndef STX_ALGORITHM_RANDOM_SHUFFLE_HPP
#define STX_ALGORITHM_RANDOM_SHUFFLE_HPP

#include <stx/algorithm/common.hpp>
#include <stx/algorithm/iter_swap.hpp>
#include <cstdlib> // rand()

namespace stx {

template <class Distance>
inline Distance random_number_impl(Distance n)
{
    return std::rand() % n;
    //return lrand48() % n;
}

template <class RandomAccessIterator>
inline void
random_shuffle(RandomAccessIterator first, RandomAccessIterator last)
{
    if (first == last) {
        return;
    }
    for (RandomAccessIterator i = first + 1; i != last; ++i) {
        iter_swap(i, first + random_number_impl((i - first) + 1));
    }
}

template <class RandomAccessIterator, class RandomNumberGenerator>
inline void
random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand)
{
    if (first == last) {
        return;
    }
    for (RandomAccessIterator i = first + 1; i != last; ++i) {
        iter_swap(i, first + rand((i - first) + 1));
    }
}

} // namespace stx

#endif // STX_ALGORITHM_RANDOM_SHUFFLE_HPP
